package algorithm.middle;

import java.util.*;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: TopKFrequent347
 * @description: 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 * 提示：
 *
 *     你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 *     你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 *     题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 *     你可以按任意顺序返回答案。
 *
 * @date 2020/9/719:51
 * @since V1.0
 */
public class TopKFrequent347 {
    public static void main(String[] args) {

    }

    public int[] topKFrequent(int[] nums, int k) {
        //把数字作为key装map，value为次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0;i<nums.length;i++){
           if(map.containsKey(nums[i])){
               map.put(nums[i],map.get(nums[i])+1);
           }else {
               map.put(nums[i],1);
           }
        }
        //使用二叉堆，由小到大
        PriorityQueue pq = new PriorityQueue<>( Comparator.comparing(map::get));



//      由小到大
//        PriorityQueue pq = new PriorityQueue<>((o1,o2)-> map.get(o1).compareTo(map.get(o2)));
//      由大到小，则无法使用::的表达式
//        PriorityQueue pq = new PriorityQueue<>((o1,o2)-> map.get(o2).compareTo(map.get(o1)));
//
//
//        PriorityQueue pq = new PriorityQueue<>(new Comparator<Integer>(){
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return map.get(o1)-map.get(o2);
//            }
//        });

        for (Integer key:map.keySet()){
            if (pq.size()<k){
                pq.add(key);
            }else {
                if (map.get(key) > map.get(pq.peek())){
                    pq.remove()
;                   pq.add(key);
                }
            }
        }

        // 取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add((Integer) pq.remove());
        }

        //list转数组
        int[] ints = res.stream().mapToInt(Integer::valueOf).toArray();
        return ints;
    }
}
